package leetcode.editor.cn.q1_300.q200;
//给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。 
//
// 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使
//用。 
//
// 
//
// 示例 1： 
// 
// 
//输入：board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,
//l,v]], words = [oath,pea,eat,rain]
//输出：[eat,oath]
// 
//
// 示例 2： 
// 
// 
//输入：board = [[a,b],[c,d]], words = [abcb]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 12 
// board[i][j] 是一个小写英文字母 
// 1 <= words.length <= 3 * 10⁴ 
// 1 <= words[i].length <= 10 
// words[i] 由小写英文字母组成 
// words 中的所有字符串互不相同 
//

import java.util.ArrayList;
import java.util.List;

/**
 * 递归不行，会超时
 */
public class Q212_WordSearchIi_REC {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int[][] arr;
        int m;
        int n;

        public List<String> findWords(char[][] board, String[] words) {

            m = board.length;
            n = board[0].length;
            List<String> list = new ArrayList<>();
            for (String word : words) {
                if (existWord(board, word)) {
                    list.add(word);
                }
            }
            return list;
        }

        private boolean existWord(char[][] board, String word) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == word.charAt(0)) {
                        arr = new int[m][n];
                        arr[i][j] = 1;
                        if (rec(board, i, j, word, 1)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        private boolean rec(char[][] board, int i, int j, String word, int cur) {
            if (cur == word.length()) {
                return true;
            }
            char c = word.charAt(cur);
            if (i - 1 >= 0 && arr[i - 1][j] != 1 && board[i - 1][j] == c) { // 上
                arr[i - 1][j] = 1;
                if (rec(board, i - 1, j, word, cur + 1)) return true;
                arr[i - 1][j] = 0;
            }
            if (i + 1 < m && arr[i + 1][j] != 1 && board[i + 1][j] == c) { // 下
                arr[i + 1][j] = 1;
                if (rec(board, i + 1, j, word, cur + 1)) return true;
                arr[i + 1][j] = 0;
            }
            if (j - 1 >= 0 && arr[i][j - 1] != 1 && board[i][j - 1] == c) { // 左
                arr[i][j - 1] = 1;
                if (rec(board, i, j - 1, word, cur + 1)) return true;
                arr[i][j - 1] = 0;
            }
            if (j + 1 < n && arr[i][j + 1] != 1 && board[i][j + 1] == c) { // 右
                arr[i][j + 1] = 1;
                if (rec(board, i, j + 1, word, cur + 1)) return true;
                arr[i][j + 1] = 0;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q212_WordSearchIi_REC().new Solution();
        // TO TEST
        char[][] board = {{'o', 'a', 'a', 'n' }, {'e', 't', 'a', 'e' }, {'i', 'h', 'k', 'r' }, {'i', 'f', 'l', 'v' }};
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println(solution.findWords(board, words));

        board = new char[][]{{'a', 'b' }, {'c', 'd' }};
        words = new String[]{"abcd"};
        System.out.println(solution.findWords(board, words));

        board = new char[][]{{'a', 'b' }, {'a', 'a' }};
        words = new String[]{"aba", "baa", "bab", "aaab", "aaa", "aaaa", "aaba"};
        System.out.println(solution.findWords(board, words));
    }
}